/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-11-23
 * Time: 23:25
 */
public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int length=nums.length;
        int left=0;
        int right=length-1;
        int lowIndex=-1;
        int highIndex=-1;
        //先找左边界
        while(left<=right){
            int mid=(left+right)>>1;
            if(nums[mid]<target){
                left=mid+1;
            }else if(target<nums[mid]){
                right=mid-1;
            }else{
                //找到target了
                //判断mid本身是不是左边界
                if(mid==0||mid>0&&nums[mid-1]<nums[mid]){
                    //mid就是左边界
                    lowIndex=mid;
                    break;
                }else{
                    //本身不是左边界,区间换为左半部分
                    right=mid-1;
                }
            }
        }
        left=0;
        right=length-1;
        //再找右边界
        while(left<=right){
            int mid=(left+right)>>1;
            if(nums[mid]<target){
                left=mid+1;
            }else if(target<nums[mid]){
                right=mid-1;
            }else{
                //判断mid本身是不是右边界
                if(mid==length-1||mid<length-1&&nums[mid]<nums[mid+1]){
                    //本身就是右边界
                    highIndex=mid;
                    break;
                }else{
                    //本身不是右边界,区间换为右半部分
                    left=mid+1;
                }
            }
        }
        return new int[]{lowIndex,highIndex};
    }
}
